#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include "BinaryTreeNode.h"
#include <iostream>
#include <queue>


//类声明
template<class T>
class BinaryTree
{
private:
	BinaryTreeNode<T>* rootNode;
public:
	BinaryTree();
	BinaryTree(T value);
	~BinaryTree();
	BinaryTreeNode<T>* getRoot(){return rootNode;}
	void inorder(BinaryTreeNode<T>* x);
	void inorder();
	void preorder(BinaryTreeNode<T>* x);
	void preorder();
	void postorder(BinaryTreeNode<T>* x);
	void postorder();
	void treeInsert(T value);
	BinaryTreeNode<T>* treeSearch(T k);
	int getHeight(BinaryTreeNode<T>* x);
	int getHeight();
	int getLeafNum(BinaryTreeNode<T>* x);
	int getLeafNum();
	void removeSubtree(BinaryTreeNode<T>* x);
	void swapChil(BinaryTreeNode<T>* x);
	void swapChil();
	BinaryTree<T>* clone();
	void cloneFromNode(BinaryTreeNode<T>* x,BinaryTreeNode<T>* tar);
	void printNodeByLevel(BinaryTreeNode<T>* x);
	void printNodeByLevel();
};

using std::cout;
using std::endl;
using std::queue;


//构造函数
template<class T>
BinaryTree<T>::BinaryTree(T value)
{
	rootNode = new BinaryTreeNode<T>(value);
}

template<class T>
BinaryTree<T>::BinaryTree()
{
	rootNode = NULL;
}

//析构函数
template<class T>
BinaryTree<T>::~BinaryTree()
{
	if(rootNode == NULL)
		return;
	removeSubtree(rootNode);
}


//按后序遍历删除一颗树
template<class T>
void BinaryTree<T>::removeSubtree(BinaryTreeNode<T>* x)
{
	if(x == NULL)
		return;	// Nothing to do
	
	removeSubtree(x->leftNode);
	removeSubtree(x->rightNode);
	cout<<"node " << x->nodeKey << " deleted!"<<endl;
	delete x;
	x=NULL;
	
}


//先序遍历
template<class T>
void BinaryTree<T>::preorder(BinaryTreeNode<T>* x)
{
	if(x != NULL)
	{
		cout << x->nodeKey << " ";
		preorder(x->leftNode);
		preorder(x->rightNode);
	}
}
template<class T>
void BinaryTree<T>::preorder()
{
	preorder(this->rootNode);
}


//中序遍历
template<class T>
void BinaryTree<T>::inorder(BinaryTreeNode<T>* x)
{
	if(x != NULL)
	{
		inorder(x->leftNode);
		cout << x->nodeKey << " ";
		inorder(x->rightNode);
	}
}
template<class T>
void BinaryTree<T>::inorder()
{
	inorder(this->rootNode);
}


//后序遍历
template<class T>
void BinaryTree<T>::postorder(BinaryTreeNode<T>* x)
{
	if(x != NULL)
	{
		postorder(x->leftNode);
		postorder(x->rightNode);
		cout << x->nodeKey << " ";
	}
}
template<class T>
void BinaryTree<T>::postorder()
{
	postorder(this->rootNode);
}


//向二叉搜索树中插入一个子节点
template<class T>
void BinaryTree<T>::treeInsert(T value)
{
	BinaryTreeNode<T>* node = new BinaryTreeNode<T>(value);
	BinaryTreeNode<T>* y = NULL;
	BinaryTreeNode<T>* x = rootNode;
	
	while(x != NULL)
	{
		y = x;
		if(node->nodeKey < x->nodeKey)
			x = x->leftNode;
		else
			x = x->rightNode;
	}
	node->parentNode = y;
	
	if(y == NULL)
	{
		rootNode = node; 	//树为空
	} else if (node->nodeKey < y->nodeKey)
	{
		y->leftNode = node;
	} else
	{
		y->rightNode = node;
	}
}


//搜索
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::treeSearch(T k)
{
	BinaryTreeNode<T>* x = rootNode;
	if(x == NULL) return NULL;
	
	while(x != NULL && x->nodeKey != k)
	{
		if (k < x->nodeKey)
			x = x->leftNode;
		else
			x = x->rightNode;
	}
	return x;
}

//获取树的高度
template<class T>
int BinaryTree<T>::getHeight(BinaryTreeNode<T>* x)
{
	static int count=0;
	static int max=0;
	if (x == NULL)
	{
		return max;
	}

	count++;
	if (count>max)
	{
		max=count;
	}
	getHeight(x->leftNode);
	getHeight(x->rightNode);
	count--;
	return max;
}
template<class T>
int BinaryTree<T>::getHeight()
{
	return getHeight(this->rootNode);
}


//获取叶子数
template<class T>
int BinaryTree<T>::getLeafNum(BinaryTreeNode<T>* x)
{
	static int count=0;
	if (x == NULL)
	{
		return count;
	}
	if (x->leftNode == NULL&&x->rightNode==NULL)
	{
		count++;
		return count;
	}
	getLeafNum(x->leftNode);
	getLeafNum(x->rightNode);
	return count;
}
template<class T>
int BinaryTree<T>::getLeafNum()
{
	return getLeafNum(this->rootNode);
}


//复制二叉树
template<class T>
BinaryTree<T>* BinaryTree<T>::clone()
{
	if ((this->rootNode) == NULL)
	{
		BinaryTree<T>* tar = new BinaryTree();
		return tar;
	}
	BinaryTree<T>* tar = new BinaryTree(this->rootNode->nodeKey);
	cloneFromNode(this->rootNode,tar->rootNode);
	return tar;
}
template<class T>
void BinaryTree<T>::cloneFromNode(BinaryTreeNode<T>* x,BinaryTreeNode<T>* tar)
{
	if (x == NULL)
	{
		return;
	}

	if ((x->leftNode) != NULL)
	{
		tar->leftNode = new BinaryTreeNode<T>(x->leftNode->nodeKey);
		tar->leftNode->parentNode = tar;
	}
	if ((x->rightNode) != NULL)
	{
		tar->rightNode = new BinaryTreeNode<T>(x->rightNode->nodeKey);
		tar->rightNode->parentNode = tar;
	}
	cloneFromNode(x->leftNode,tar->leftNode);
	cloneFromNode(x->rightNode,tar->rightNode);
}


//用先序遍历交换左右子树
template<class T>
void BinaryTree<T>::swapChil(BinaryTreeNode<T>* x)
{
	if (x == NULL)
	{
		return;
	}
	BinaryTreeNode<T>* temp=(x->rightNode);
	(x->rightNode)=(x->leftNode);
	(x->leftNode)=temp;
	swapChil(x->leftNode);
	swapChil(x->rightNode);
}
template<class T>
void BinaryTree<T>::swapChil()
{
	swapChil(this->rootNode);
}


//层序遍历
template<class T>
void BinaryTree<T>::printNodeByLevel(BinaryTreeNode<T>* x)
{
    if(x == NULL)
        return;

    queue<BinaryTreeNode<T>*> que;
    que.push(x);
    int num;

    while(que.front() != NULL)
    {
		num = que.size();
        for (int i = 0; i < num; ++i)
        {
        	cout<<que.front()->nodeKey<<" ";
            if(que.front()->rightNode != NULL)
                que.push(que.front()->rightNode);
            if(que.front()->leftNode != NULL)
                que.push(que.front()->leftNode);
            que.pop();
        }
        cout<<endl;

    }
}
template<class T>
void BinaryTree<T>::printNodeByLevel()
{
	printNodeByLevel(this->rootNode);
}




//233333



#endif //BINARY_TREE_H
